package com.cet.algorithm.回溯.重新安排行程;

import java.util.*;

/**
 * @program: cet-practice
 * @description: 恢复行程路线
 * @author: 陈恩涛
 * @create: 2023-06-03 22:59
 **/
public class Solution {

    public static void main(String[] args) {
        List<List<String>> tickets = new ArrayList<>();
        tickets.add(Arrays.asList("JFK", "KUL"));
        tickets.add(Arrays.asList("JFK", "NRT"));
        tickets.add(Arrays.asList("NRT", "JFK"));
        tickets.add(Arrays.asList("JFK", "NRT"));
        tickets.add(Arrays.asList("NRT", "JFK"));

        Solution solution = new Solution();
        System.out.println(solution.findItinerary(tickets));
    }

    private List<String> result;

    private final LinkedList<String> path = new LinkedList<>();

    private boolean[] used;

    public List<String> findItinerary(List<List<String>> tickets) {
        used = new boolean[tickets.size()];

        // 根据航班的目的地进行排序，保证相同出发地，字典排序优先
        tickets.sort(Comparator.comparing(route -> route.get(1)));
        path.add("JFK");
        backTracing(tickets);
        return result;

    }

    private boolean backTracing(List<List<String>> tickets) {

        // 递归终止条件
        if (path.size() == tickets.size() + 1) {
            result = new LinkedList<>(path);
            return true;
        }

        //单层递归逻辑
        for (int i = 0; i < tickets.size(); i++) {

            // !used[i]防止死循环，保证每个航班路线只使用一次
            if (!used[i] && path.getLast().equals(tickets.get(i).get(0))) {
                path.add(tickets.get(i).get(1));
                used[i] = true;
                if (backTracing(tickets)) {
                    return true;
                }
                used[i] = false;
                path.removeLast();
            }
        }

        return false;
    }
}
